home *** CD-ROM | disk | FTP | other *** search
/ Gekikoh Dennoh Club 5 / Gekikoh Dennoh Club Vol. 5 (Japan).7z / Gekikoh Dennoh Club Vol. 5 (Japan) (Track 01).bin / internet / xip / iijppp.lzh / src / slcompress.c < prev    next >
C/C++ Source or Header  |  1994-09-25  |  16KB  |  588 lines
  1. /*
  2.  * Routines to compress and uncompess tcp packets (for transmission
  3.  * over low speed serial lines.
  4.  *
  5.  * Copyright (c) 1989 Regents of the University of California.
  6.  * All rights reserved.
  7.  *
  8.  * Redistribution and use in source and binary forms are permitted
  9.  * provided that the above copyright notice and this paragraph are
  10.  * duplicated in all such forms and that any documentation,
  11.  * advertising materials, and other materials related to such
  12.  * distribution and use acknowledge that the software was developed
  13.  * by the University of California, Berkeley.  The name of the
  14.  * University may not be used to endorse or promote products derived
  15.  * from this software without specific prior written permission.
  16.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  17.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  18.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  19.  *
  20.  *    Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
  21.  *    - Initial distribution.
  22.  */
  23. #ifndef lint
  24. static char rcsid[] = "$Header";
  25. #endif
  26.  
  27. #include "defs.h"
  28. #include <netinet/in_systm.h>
  29. #include <netinet/in.h>
  30. #include <netinet/tcp.h>
  31. #include <netinet/ip.h>
  32. #include "slcompress.h"
  33.  
  34. struct slstat slstat;
  35.  
  36. #define INCR(counter)    slstat.counter++;
  37.  
  38. #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n))
  39. #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n))
  40. #ifndef KERNEL
  41. #define ovbcopy bcopy
  42. #endif
  43.  
  44. static int reason1, reason2, reason3, reason4, reason5;
  45.  
  46. void
  47. sl_compress_init(comp)
  48.     struct slcompress *comp;
  49. {
  50.     register u_int i;
  51.     register struct cstate *tstate = comp->tstate;
  52.  
  53.     bzero((char *)comp, sizeof(*comp));
  54.     for (i = MAX_STATES - 1; i > 0; --i) {
  55.         tstate[i].cs_id = i;
  56.         tstate[i].cs_next = &tstate[i - 1];
  57.     }
  58.     tstate[0].cs_next = &tstate[MAX_STATES - 1];
  59.     tstate[0].cs_id = 0;
  60.     comp->last_cs = &tstate[0];
  61.     comp->last_recv = 255;
  62.     comp->last_xmit = 255;
  63.     comp->flags = SLF_TOSS;
  64. }
  65.  
  66.  
  67. /* ENCODE encodes a number that is known to be non-zero.  ENCODEZ
  68.  * checks for zero (since zero has to be encoded in the long, 3 byte
  69.  * form).
  70.  */
  71. #define ENCODE(n) { \
  72.     if ((u_short)(n) >= 256) { \
  73.         *cp++ = 0; \
  74.         cp[1] = (n); \
  75.         cp[0] = (n) >> 8; \
  76.         cp += 2; \
  77.     } else { \
  78.         *cp++ = (n); \
  79.     } \
  80. }
  81. #define ENCODEZ(n) { \
  82.     if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
  83.         *cp++ = 0; \
  84.         cp[1] = (n); \
  85.         cp[0] = (n) >> 8; \
  86.         cp += 2; \
  87.     } else { \
  88.         *cp++ = (n); \
  89.     } \
  90. }
  91.  
  92. #define DECODEL(f) { \
  93.     if (*cp == 0) {\
  94.         (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
  95.         cp += 3; \
  96.     } else { \
  97.         (f) = htonl(ntohl(f) + (u_long)*cp++); \
  98.     } \
  99. }
  100.  
  101. #define DECODES(f) { \
  102.     if (*cp == 0) {\
  103.         (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
  104.         cp += 3; \
  105.     } else { \
  106.         (f) = htons(ntohs(f) + (u_long)*cp++); \
  107.     } \
  108. }
  109.  
  110. #define DECODEU(f) { \
  111.     if (*cp == 0) {\
  112.         (f) = htons((cp[1] << 8) | cp[2]); \
  113.         cp += 3; \
  114.     } else { \
  115.         (f) = htons((u_long)*cp++); \
  116.     } \
  117. }
  118.  
  119.  
  120. u_char
  121. sl_compress_tcp(m, ip, comp, compress_cid)
  122.     struct mbuf *m;
  123.     register struct ip *ip;
  124.     struct slcompress *comp;
  125.     int compress_cid;
  126. {
  127.     register struct cstate *cs = comp->last_cs->cs_next;
  128.     register u_int hlen = ip->ip_hl;
  129.     register struct tcphdr *oth;
  130.     register struct tcphdr *th;
  131.     register u_int deltaS, deltaA;
  132.     register u_int changes = 0;
  133.     u_char new_seq[16];
  134.     register u_char *cp = new_seq;
  135.  
  136.     /*
  137.      * Bail if this is an IP fragment or if the TCP packet isn't
  138.      * `compressible' (i.e., ACK isn't set or some other control bit is
  139.      * set).  (We assume that the caller has already made sure the
  140.      * packet is IP proto TCP).
  141.      */
  142. #ifdef DEBUG
  143.     if ((ip->ip_off & htons(0x3fff)) || m->cnt < 40) {
  144.         logprintf("??? 1 ip_off = %x, cnt = %d\n", ip->ip_off, m->cnt);
  145.         DumpBp(m);
  146.         return (TYPE_IP);
  147.     }
  148. #else
  149.     if ((ip->ip_off & htons(0x3fff)) || m->cnt < 40)
  150.         return (TYPE_IP);
  151. #endif
  152.  
  153.     th = (struct tcphdr *)&((int *)ip)[hlen];
  154. #ifdef DEBUG
  155.     if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK) {
  156.         logprintf("??? 2 th_flags = %x\n", th->th_flags);
  157.         DumpBp(m);
  158.         return (TYPE_IP);
  159.     }
  160. #else
  161.     if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK)
  162.         return (TYPE_IP);
  163. #endif
  164.  
  165.     /*
  166.      * Packet is compressible -- we're going to send either a
  167.      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way we need
  168.      * to locate (or create) the connection state.  Special case the
  169.      * most recently used connection since it's most likely to be used
  170.      * again & we don't have to do any reordering if it's used.
  171.      */
  172.     INCR(sls_packets)
  173.     if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
  174.         ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
  175.         *(int *)th != ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl]) {
  176.         /*
  177.          * Wasn't the first -- search for it.
  178.          *
  179.          * States are kept in a circularly linked list with
  180.          * last_cs pointing to the end of the list.  The
  181.          * list is kept in lru order by moving a state to the
  182.          * head of the list whenever it is referenced.  Since
  183.          * the list is short and, empirically, the connection
  184.          * we want is almost always near the front, we locate
  185.          * states via linear search.  If we don't find a state
  186.          * for the datagram, the oldest state is (re-)used.
  187.          */
  188.         register struct cstate *lcs;
  189.         register struct cstate *lastcs = comp->last_cs;
  190.  
  191.         do {
  192.             lcs = cs; cs = cs->cs_next;
  193.             INCR(sls_searches)
  194.             if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr
  195.                 && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr
  196.                 && *(int *)th == ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl])
  197.                 goto found;
  198.         } while (cs != lastcs);
  199.  
  200.         /*
  201.          * Didn't find it -- re-use oldest cstate.  Send an
  202.          * uncompressed packet that tells the other side what
  203.          * connection number we're using for this conversation.
  204.          * Note that since the state list is circular, the oldest
  205.          * state points to the newest and we only need to set
  206.          * last_cs to update the lru linkage.
  207.          */
  208.         INCR(sls_misses)
  209.         comp->last_cs = lcs;
  210. #define    THOFFSET(th)    (th->th_off)
  211.         hlen += th->th_off;
  212.         hlen <<= 2;
  213.         if (hlen > m->cnt)
  214.             return(TYPE_IP);
  215. reason1++;
  216.         goto uncompressed;
  217.  
  218.     found:
  219.         /*
  220.          * Found it -- move to the front on the connection list.
  221.          */
  222.         if (cs == lastcs)
  223.             comp->last_cs = lcs;
  224.         else {
  225.             lcs->cs_next = cs->cs_next;
  226.             cs->cs_next = lastcs->cs_next;
  227.             lastcs->cs_next = cs;
  228.         }
  229.     }
  230.  
  231.     /*
  232.      * Make sure that only what we expect to change changed. The first
  233.      * line of the `if' checks the IP protocol version, header length &
  234.      * type of service.  The 2nd line checks the "Don't fragment" bit.
  235.      * The 3rd line checks the time-to-live and protocol (the protocol
  236.      * check is unnecessary but costless).  The 4th line checks the TCP
  237.      * header length.  The 5th line checks IP options, if any.  The 6th
  238.      * line checks TCP options, if any.  If any of these things are
  239.      * different between the previous & current datagram, we send the
  240.      * current datagram `uncompressed'.
  241.      */
  242.     oth = (struct tcphdr *)&((int *)&cs->cs_ip)[hlen];
  243.     deltaS = hlen;
  244.     hlen += th->th_off;
  245.     hlen <<= 2;
  246.     if (hlen > m->cnt)
  247.         return(TYPE_IP);
  248.  
  249.     if (((u_short *)ip)[0] != ((u_short *)&cs->cs_ip)[0] ||
  250.         ((u_short *)ip)[3] != ((u_short *)&cs->cs_ip)[3] ||
  251.         ((u_short *)ip)[4] != ((u_short *)&cs->cs_ip)[4] ||
  252.         THOFFSET(th) != THOFFSET(oth) ||
  253.         (deltaS > 5 &&
  254.          BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
  255.         (THOFFSET(th) > 5 &&
  256.          BCMP(th + 1, oth + 1, (THOFFSET(th) - 5) << 2))) {
  257. reason2++;
  258.         goto uncompressed;
  259.     }
  260.  
  261.     /*
  262.      * Figure out which of the changing fields changed.  The
  263.      * receiver expects changes in the order: urgent, window,
  264.      * ack, seq (the order minimizes the number of temporaries
  265.      * needed in this section of code).
  266.      */
  267.     if (th->th_flags & TH_URG) {
  268.         deltaS = ntohs(th->th_urp);
  269.         ENCODEZ(deltaS);
  270.         changes |= NEW_U;
  271.     } else if (th->th_urp != oth->th_urp) {
  272.         /* argh! URG not set but urp changed -- a sensible
  273.          * implementation should never do this but RFC793
  274.          * doesn't prohibit the change so we have to deal
  275.          * with it. */
  276. reason3++;
  277.          goto uncompressed;
  278.     }
  279.  
  280.     deltaS = (u_short)(ntohs(th->th_win) - ntohs(oth->th_win));
  281.     if (deltaS) {
  282.         ENCODE(deltaS);
  283.         changes |= NEW_W;
  284.     }
  285.  
  286.     deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack);
  287.     if (deltaA) {
  288.         if (deltaA > 0xffff) {
  289. reason4++;
  290.             goto uncompressed;
  291.         }
  292.         ENCODE(deltaA);
  293.         changes |= NEW_A;
  294.     }
  295.  
  296.     deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq);
  297.     if (deltaS) {
  298.         if (deltaS > 0xffff) {
  299.             reason4++;
  300.             goto uncompressed;
  301.         }
  302.         ENCODE(deltaS);
  303.         changes |= NEW_S;
  304.     }
  305.  
  306.     switch(changes) {
  307.  
  308.     case 0:
  309.         /*
  310.          * Nothing changed. If this packet contains data and the
  311.          * last one didn't, this is probably a data packet following
  312.          * an ack (normal on an interactive connection) and we send
  313.          * it compressed.  Otherwise it's probably a retransmit,
  314.          * retransmitted ack or window probe.  Send it uncompressed
  315.          * in case the other side missed the compressed version.
  316.          */
  317.         if (ip->ip_len != cs->cs_ip.ip_len &&
  318.             ntohs(cs->cs_ip.ip_len) == hlen)
  319.             break;
  320.  
  321.         /* (fall through) */
  322.  
  323.     case SPECIAL_I:
  324.     case SPECIAL_D:
  325.         /*
  326.          * actual changes match one of our special case encodings --
  327.          * send packet uncompressed.
  328.          */
  329. reason5++;
  330.         goto uncompressed;
  331.  
  332.     case NEW_S|NEW_A:
  333.         if (deltaS == deltaA &&
  334.             deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
  335.             /* special case for echoed terminal traffic */
  336.             changes = SPECIAL_I;
  337.             cp = new_seq;
  338.         }
  339.         break;
  340.  
  341.     case NEW_S:
  342.         if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
  343.             /* special case for data xfer */
  344.             changes = SPECIAL_D;
  345.             cp = new_seq;
  346.         }
  347.         break;
  348.     }
  349.  
  350.     deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
  351.     if (deltaS != 1) {
  352.         ENCODEZ(deltaS);
  353.         changes |= NEW_I;
  354.     }
  355.     if (th->th_flags & TH_PUSH)
  356.         changes |= TCP_PUSH_BIT;
  357.     /*
  358.      * Grab the cksum before we overwrite it below.  Then update our
  359.      * state with this packet's header.
  360.      */
  361.     deltaA = ntohs(th->th_sum);
  362.     BCOPY(ip, &cs->cs_ip, hlen);
  363.  
  364.     /*
  365.      * We want to use the original packet as our compressed packet.
  366.      * (cp - new_seq) is the number of bytes we need for compressed
  367.      * sequence numbers.  In addition we need one byte for the change
  368.      * mask, one for the connection id and two for the tcp checksum.
  369.      * So, (cp - new_seq) + 4 bytes of header are needed.  hlen is how
  370.      * many bytes of the original packet to toss so subtract the two to
  371.      * get the new packet size.
  372.      */
  373.     deltaS = cp - new_seq;
  374.     cp = (u_char *)ip;
  375.  
  376.         /*
  377.          * Since fastq traffic can jump ahead of the background traffic,
  378.          * we don't know what order packets will go on the line.  In this
  379.          * case, we always send a "new" connection id so the receiver state
  380.          * stays synchronized.
  381.          */
  382. #ifdef SL_NOFASTQ
  383.         if (comp->last_xmit == cs->cs_id) {
  384.                 hlen -= deltaS + 3;
  385.                 cp += hlen;
  386.                 *cp++ = changes;
  387.         } else
  388. #endif
  389.     {
  390.         comp->last_xmit = cs->cs_id;
  391.         hlen -= deltaS + 4;
  392.         cp += hlen;
  393.         *cp++ = changes | NEW_C;
  394.         *cp++ = cs->cs_id;
  395.     }
  396.     m->cnt -= hlen;
  397.     m->offset += hlen;
  398.     *cp++ = deltaA >> 8;
  399.     *cp++ = deltaA;
  400.     BCOPY(new_seq, cp, deltaS);
  401.     INCR(sls_compressed)
  402.     return (TYPE_COMPRESSED_TCP);
  403.  
  404.     /*
  405.      * Update connection state cs & send uncompressed packet ('uncompressed'
  406.      * means a regular ip/tcp packet but with the 'conversation id' we hope
  407.      * to use on future compressed packets in the protocol field).
  408.      */
  409. uncompressed:
  410.     BCOPY(ip, &cs->cs_ip, hlen);
  411.     ip->ip_p = cs->cs_id;
  412.     comp->last_xmit = cs->cs_id;
  413.     return (TYPE_UNCOMPRESSED_TCP);
  414. }
  415.  
  416.  
  417. int
  418. sl_uncompress_tcp(bufp, len, type, comp)
  419.     u_char **bufp;
  420.     int len;
  421.     u_int type;
  422.     struct slcompress *comp;
  423. {
  424.     register u_char *cp;
  425.     register u_int hlen, changes;
  426.     register struct tcphdr *th;
  427.     register struct cstate *cs;
  428.     register struct ip *ip;
  429.  
  430.     switch (type) {
  431.  
  432.     case TYPE_UNCOMPRESSED_TCP:
  433.         ip = (struct ip *) *bufp;
  434.         if (ip->ip_p >= MAX_STATES)
  435.             goto bad;
  436.         cs = &comp->rstate[comp->last_recv = ip->ip_p];
  437.         comp->flags &=~ SLF_TOSS;
  438.         ip->ip_p = IPPROTO_TCP;
  439.         hlen = ip->ip_hl;
  440.         th = (struct tcphdr *)&((int *)ip)[hlen];
  441.         hlen += THOFFSET(th);
  442.         hlen <<= 2;
  443.         BCOPY(ip, &cs->cs_ip, hlen);
  444.         cs->cs_ip.ip_sum = 0;
  445.         cs->cs_hlen = hlen;
  446.         INCR(sls_uncompressedin)
  447.         return (len);
  448.  
  449.     default:
  450.         goto bad;
  451.  
  452.     case TYPE_COMPRESSED_TCP:
  453.         break;
  454.     }
  455.     /* We've got a compressed packet. */
  456.     INCR(sls_compressedin)
  457.     cp = *bufp;
  458.     changes = *cp++;
  459. #ifdef DEBUG
  460.     logprintf("compressed: changes = %02x\n", changes);
  461. #endif
  462.     if (changes & NEW_C) {
  463.         /* Make sure the state index is in range, then grab the state.
  464.          * If we have a good state index, clear the 'discard' flag. */
  465.         if (*cp >= MAX_STATES)
  466.             goto bad;
  467.  
  468.         comp->flags &=~ SLF_TOSS;
  469.         comp->last_recv = *cp++;
  470.     } else {
  471.         /* this packet has an implicit state index.  If we've
  472.          * had a line error since the last time we got an
  473.          * explicit state index, we have to toss the packet. */
  474.         if (comp->flags & SLF_TOSS) {
  475.             INCR(sls_tossed)
  476.             return (0);
  477.         }
  478.     }
  479.     cs = &comp->rstate[comp->last_recv];
  480.     hlen = cs->cs_ip.ip_hl << 2;
  481.     th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen];
  482.     th->th_sum = htons((*cp << 8) | cp[1]);
  483.     cp += 2;
  484.     if (changes & TCP_PUSH_BIT)
  485.         th->th_flags |= TH_PUSH;
  486.     else
  487.         th->th_flags &=~ TH_PUSH;
  488.  
  489.     switch (changes & SPECIALS_MASK) {
  490.     case SPECIAL_I:
  491.         {
  492.         register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
  493.         th->th_ack = htonl(ntohl(th->th_ack) + i);
  494.         th->th_seq = htonl(ntohl(th->th_seq) + i);
  495.         }
  496.         break;
  497.  
  498.     case SPECIAL_D:
  499.         th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
  500.                    - cs->cs_hlen);
  501.         break;
  502.  
  503.     default:
  504.         if (changes & NEW_U) {
  505.             th->th_flags |= TH_URG;
  506.             DECODEU(th->th_urp)
  507.         } else
  508.             th->th_flags &=~ TH_URG;
  509.         if (changes & NEW_W)
  510.             DECODES(th->th_win)
  511.         if (changes & NEW_A)
  512.             DECODEL(th->th_ack)
  513.         if (changes & NEW_S) {
  514. #ifdef DEBUG
  515.           logprintf("NEW_S: %02x, %02x, %02x\r\n", *cp, cp[1], cp[2]);
  516. #endif
  517.             DECODEL(th->th_seq)
  518.         }
  519.         break;
  520.     }
  521.     if (changes & NEW_I) {
  522.         DECODES(cs->cs_ip.ip_id)
  523.     } else
  524.         cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
  525. #ifdef DEBUG
  526.     logprintf("id = %04x, seq = %08x\r\n", cs->cs_ip.ip_id, ntohl(th->th_seq));
  527. #endif
  528.  
  529.     /*
  530.      * At this point, cp points to the first byte of data in the
  531.      * packet.  If we're not aligned on a 4-byte boundary, copy the
  532.      * data down so the ip & tcp headers will be aligned.  Then back up
  533.      * cp by the tcp/ip header length to make room for the reconstructed
  534.      * header (we assume the packet we were handed has enough space to
  535.      * prepend 128 bytes of header).  Adjust the length to account for
  536.      * the new header & fill in the IP total length.
  537.      */
  538.     len -= (cp - *bufp);
  539.     if (len < 0)
  540.         /* we must have dropped some characters (crc should detect
  541.          * this but the old slip framing won't) */
  542.         goto bad;
  543.  
  544. #ifdef notdef
  545.     if ((int)cp & 3) {
  546.         if (len > 0)
  547.             (void) ovbcopy(cp, (caddr_t)((int)cp &~ 3), len);
  548.         cp = (u_char *)((int)cp &~ 3);
  549.     }
  550. #endif
  551.  
  552.     cp -= cs->cs_hlen;
  553.     len += cs->cs_hlen;
  554.     cs->cs_ip.ip_len = htons(len);
  555.     BCOPY(&cs->cs_ip, cp, cs->cs_hlen);
  556.     *bufp = cp;
  557.  
  558.     /* recompute the ip header checksum */
  559.     {
  560.         register u_short *bp = (u_short *)cp;
  561.         for (changes = 0; hlen > 0; hlen -= 2)
  562.             changes += *bp++;
  563.         changes = (changes & 0xffff) + (changes >> 16);
  564.         changes = (changes & 0xffff) + (changes >> 16);
  565.         ((struct ip *)cp)->ip_sum = ~ changes;
  566.     }
  567.     return (len);
  568. bad:
  569.     comp->flags |= SLF_TOSS;
  570.     INCR(sls_errorin)
  571.     return (0);
  572. }
  573.  
  574. int
  575. ReportCompress()
  576. {
  577.   printf("Out:  %d (compress) / %d (total)",
  578.     slstat.sls_compressed, slstat.sls_packets);
  579.   printf("  %d (miss) / %d (search)\n",
  580.     slstat.sls_misses, slstat.sls_searches);
  581.   printf("In:  %d (compress), %d (uncompress)",
  582.     slstat.sls_compressedin, slstat.sls_uncompressedin);
  583.   printf("  %d (error),  %d (tossed)\n",
  584.     slstat.sls_errorin, slstat.sls_tossed);
  585.   printf("%d, %d, %d, %d, %d\n", reason1, reason2, reason3, reason4, reason5);
  586.   return(1);
  587. }
  588.